cryptographyfandomcom-20200215-history
Block design
In combinatorial mathematics, a block design is a particular kind of hypergraph or set system, which has applications to experimental design, finite geometry, software testing, cryptography, and algebraic geometry. Many variations have been studied, including balanced incomplete block designs.Handbook of combinatorial designs. Edited by Charles J. Colbourn and Jeffrey H. Dinitz. Second edition. Discrete Mathematics and its Applications (Boca Raton). Chapman & Hall/CRC, Boca Raton, FL, 2007 Stinson, Douglas R. Combinatorial designs: Constructions and analysis. Springer-Verlag, New York, 2004. xvi+300 pp. ISBN 0-387-95487-2 Given a finite set X'' (of elements called points) and integers ''k, r'', λ ≥ 1, we define a ''2-design B'' to be a set of ''k-element subsets of X'', called ''blocks, such that the number r'' of blocks containing ''x in X'' is independent of ''x, and the number λ'' of blocks containing given distinct points ''x and y'' in ''X is also independent of the choices. Here v'' (the number of elements of ''X, called points), b'' (the number of blocks), ''k, r'', and λ are the ''parameters of the design. (Also, B'' may not consist of all ''k-element subsets of X''; that is the meaning of ''incomplete.) In a table: : The design is called a (v'', ''k, λ)-design or a (v'', ''b, r'', ''k, λ)-design. The parameters are not all independent; v'', ''k, and λ determine b'' and ''r, and not all combinations of v'', ''k, and λ are possible. The two basic equations connecting these parameters are : bk = vr, \, : \lambda(v-1) = r(k-1). \, These conditions are not sufficient as for example a (43,7,1)-design does not exist. A fundamental theorem, Fisher's inequality, named after Ronald Fisher, is that b'' ≥ ''v in any block design. The case of equality is called a symmetric design; it has many special features. Examples Examples of block designs include the lines in finite projective planes (where X'' is the set of points of the plane and λ = 1), and Steiner triple systems (k = 3 and \lambda=1) . The former is a relatively simple example of a symmetric design. Triple systems (k=3) are of interest in their own right.Colbourn, Charles J. and Rosa, Alexander, Triple systems, Oxford Mathematical Monographs,The Clarendon Press Oxford University Press, New York.1999,ISBN 0-19-853576-7 Projective planes Projective planes are a special case of block designs, where we have \scriptstyle v \,>\, 0 points and, as they are symmetric designs, \scriptstyle b \,=\, v (which is the limit case of Fisher's inequality), from the first basic equation we get : k = r, \, and since \scriptstyle \lambda \,=\, 1 by definition, the second equation gives us : v-1 = k(k-1).\, Now, given an integer \scriptstyle n \,\geq\, 1 , called the ''order of the projective plane, we can put k'' = ''n + 1 and, from the displayed equation above, we have \scriptstyle v \,=\, (n+1)n \,+\, 1 \,=\, n^2 \,+\, n \,+\, 1 points in a projective plane of order n''. Since a projective plane is symmetric, we have that \scriptstyle b \,=\, v , which means that \scriptstyle b \,=\, n^2 \,+\, n \,+\, 1 also. The number ''b is usually called the number of lines of the projective plane. This means, as a corollary, that in a projective plane, the number of lines and the number of points are always the same. For a projective plane, k'' is the number of points on each line and it is equal to ''n + 1, where n'' is the order of the plane. Similarly, ''r = n'' + 1 is the number of lines to which the a given point is incident. For ''n = 2 we get a projective plane of order 2, also called the Fano plane, with v'' = 4 + 2 + 1 = 7 points and 7 lines. In the Fano plane, each line has ''n + 1 = 3 points and each point belongs to n'' + 1 = 3 lines. Biplane geometry A '''biplane geometry' or biplane is another type of symmetric design ("projective design"), here with λ = 2 – it is a symmetric design such that any set of two points is contained in two blocks ("lines"), while any two lines intersect in two points;ATLAS of Finite Groups, p. 7 this is similar to a finite projective plane, except that rather than two points determining one line (and two lines determining one point), they determine two lines (respectively, points). A biplane geometry of order n'' is one whose blocks have k=n+2 points, by analogy with a projective plane of order ''n being one with k=n+1 points, and similarly for other projective designs. A biplane of order n'' has v=1+(k+2)(k+1)/2 points (since r=k ). As examples:Designs and their codes, by E. F. Assmus, J. D. Key, p. 126 * The order 0 biplane has 2 points (and lines of size 2 – (2,2,2)); it is two points, with two blocks, each consisting of both points. Geometrically, it is the digon. :One can also in define trivial biplane geometries of order −1 (1 point, lines of size 1 (2,1,2) – the point is contained in the line) and −2 (1 point, lines of size 0 (2,0,2) – the point is not contained in the line). * The order 1 biplane has 4 points (and lines of size 3 – (4,3,2)); it is the complete design with ''v = 4 and k'' = 3. Geometrically, the points are the vertices and the blocks are the faces of a tetrahedron. * The order 2 biplane is the complement of the Fano plane: it has 7 points (and lines of size 4 – (7,4,2)), where the lines are given as the ''complements of the (3-point) lines in the Fano plane. * The order 3 biplane has 11 points (and lines of size 5 – (11,5,2)), and is also known as the after Raymond Paley; it is associated to the Paley digraph of order 11, which is constructed using the field with 11 elements, and is associated to the order 12 Hadamard matrix; see Paley construction I. :Algebraically this corresponds to the exceptional embedding of the projective special linear group PSL(2,5) in PSL(2,11) – see [[Projective linear group#Action on p points|projective linear group: action on p'' points]] for details. * There are 3 biplanes of order 4 (16 points, lines of size 6 – (16,6,2)). * There are at least 4 biplanes of order 9 (and 56 points – (56,11,2)).[http://www.emis.de/journals/HOA/IJMMS/Volume2_2/260.pdf The Four Known Biplanes with ''k = 11] Generalization: t''-designs Given any integer ''t ≥ 2, a t''-design ''B is a class of k''-element subsets of ''X (the set of points), called blocks, such that every point x'' in ''X appears in exactly r'' blocks, and every ''t-element subset T'' appears in exactly λ blocks. The numbers ''v (the number of elements of X''), ''b (the number of blocks), k'', ''r, λ, and t'' are the ''parameters of the design. The design may be called a t''-(''v,k'',λ)-design. Again, these four numbers determine ''b and r'' and the four numbers themselves cannot be chosen arbitrarily. The equations are : b_i = \lambda \left.\binom{v-i}{t-i} \right/ \binom{k-i}{t-i} \text{ for } i = 0,1,\ldots,t, where ''bi is the number of blocks that contain any i''-element set of points. There are no known examples of non-trivial ''t-(v'',''k,1)-designs with \scriptstyle t >\, 5 . The term block design by itself usually means a 2-design. See also * Randomized block design Notes References * van Lint, J.H., and R.M. Wilson (1992), A Course in Combinatorics. Cambridge, Eng.: Cambridge University Press. * S. S. Shrikhande, and Vasanti N. Bhat-Nayak, Non-isomorphic solutions of some balanced incomplete block designs I – Journal of Combinatorial Theory, 1970 * * * * External links *Design DB: A database of combinatorial, statistical, experimental block designs Category:Design theory Category:Set families Category:Experimental design Category:Analysis of variance Category:Software testing Category:Cryptography de:Blockplan ja:ブロックデザイン (数学) ru:Блок-дизайн